/**
 * 
 */
package IndexComponent;

import java.util.*;

import PagedFile.Buffer;
import PagedFile.PF_Abort_Exception;
import PagedFile.PF_FileHandle;
import RecordManagement.RID;

/**
 * @author Neil
 *
 */
class BPlusTree implements BPlusTree_Interface{
	
	PF_FileHandle pfh;
	BPTree_FileHead fhead;
	BPlusTreeNode root;
	
	public static final byte LEAF = BPlusTreeNode.LEAF;
	public static final byte NODE = BPlusTreeNode.NODE;

	static FunctionalClass.Bit_Operation bop = new FunctionalClass.Bit_Operation();
	static FunctionalClass.Buffer_Bit_Operation bbop = new FunctionalClass.Buffer_Bit_Operation();
	
	//Create A New B+-Tree
	BPlusTree(PF_FileHandle pfh, int attrType, int attrLength) {
		this.pfh = pfh;
		fhead = new BPTree_FileHead(attrType, attrLength);
		
		//Establish and Store the B+-tree head into the file
		Buffer headBuffer = pfh.AllocatePage();
		if (headBuffer.block.pageNum!=1)
			throw new IX_Abort_Exception("Fatal");
		headBuffer.mark(this.hashCode());
		fhead.put_into_ByteBuffer(headBuffer.contents);
		headBuffer.write();
		pfh.UnpinPage(1);
		root = new BPlusTreeNode(pfh, fhead, BPlusTreeNode.LEAF);
		fhead.RootPageNum = root.pageNum;
		fhead.FirstLeafPageNum = root.pageNum;
	}

	//Load tree mega-data from the file
	BPlusTree(PF_FileHandle pfh) throws PF_Abort_Exception {
		this.pfh = pfh;
		
		// Get B+-tree Head from the file
		Buffer headBuffer = pfh.GetThisPage(1);
		fhead = new BPTree_FileHead(headBuffer.contents);
		pfh.UnpinPage(1);
		
		//Load root page from the disk
		root = new BPlusTreeNode(fhead, pfh, fhead.RootPageNum);
		
	}
	
	public void StoreHead() throws PF_Abort_Exception {
		// Store the IX FileHead into the file
		Buffer headBuffer = pfh.GetThisPage(1);
		headBuffer.mark(this.hashCode());
		fhead.put_into_ByteBuffer(headBuffer.contents);
		headBuffer.write();
		pfh.UnpinPage(headBuffer.block.pageNum);
	}
	
	void CloseTree() {
		StoreHead();
	}
	
	//Return the first occurrence leaf of the key
	BPlusTreeNode SearchLeafByKey(Keyword key) {
		BPlusTreeNode btNode = root;
		int i;
		while (btNode.type!=LEAF) {
			for (i=0; i<btNode.numOfKeyword; ++i) {
				if (btNode.GetKeyword(i).compareTo(key)>0)
					break;
			}
			btNode = new BPlusTreeNode(fhead, pfh, btNode.GetPointer(i));
		}
		return btNode;
	}

	@Override
	public void DeleteEntry(Keyword key, RID rid) {
		List<BPlusTreeNode> parentList = new ArrayList<BPlusTreeNode>();
		BPlusTreeNode leaf = root;
		int i;
		while (leaf.type != LEAF) {
			for (i=0; i<leaf.numOfKeyword; ++i) {
				if (leaf.GetKeyword(i).compareTo(key)>0)
					break;
			}
			parentList.add(leaf);
			leaf = new BPlusTreeNode(fhead, pfh, leaf.GetPointer(i));
		}
		/*
		 * There are different conditions:
		 * 1. leaf is root. delete keyword and do nothing else.
		 * 2. key deleted is not the first key. Just deleted and jump 4.
		 * 3. key deleted is the first key. delete key and refresh parent nodes.
		 * 4. leaf has not enough keys and need to merge.
		 */
		if ( leaf.DeleteFromLeaf(key, rid) == null )
			throw new IX_Abort_Exception("Key Not Exists");
		
		if ( leaf == root ) //condition 1
			return;
		
		if ( leaf.GetKeyword(0).equals(key) ) //condition 3
			this.Refresh(leaf.GetKeyword(0), leaf.pageNum, parentList);
		
		if ( leaf.numOfKeyword < (fhead.Level+1)/2 ) { //A merge is needed.
			assert(leaf.numOfKeyword == (fhead.Level-1)/2);
			if (leaf.nextPageNum>0 && 
					parentList.get(parentList.size()-1).isPredecessor(leaf.nextPageNum, leaf.pageNum))
			{ //try to merge with right leaf.
				BPlusTreeNode rightLeaf = new BPlusTreeNode(fhead, pfh, leaf.nextPageNum);
				MergeTwoLeaves(leaf, rightLeaf, parentList);
				return;
			}
			if (leaf.prePageNum>0 &&
					parentList.get(parentList.size()-1).isPredecessor(leaf.pageNum, leaf.prePageNum))
			{ //try to merge with left leaf.
				BPlusTreeNode leftLeaf = new BPlusTreeNode(fhead, pfh, leaf.prePageNum);
				MergeTwoLeaves(leftLeaf, leaf, parentList);
				return;
			}
			throw new IX_Abort_Exception("Fatal");
		}
	}
	
	private void MergeTwoLeaves(BPlusTreeNode left, BPlusTreeNode right, List<BPlusTreeNode> parentList) {
		if (left.numOfKeyword>(fhead.Level+3)/2) { //put the rightmost key into right
			KeywordDataPair kdp = left.RemoveKeyDataPair(left.numOfKeyword-1);
			right.AddKeyDataPair(0, kdp);
			this.Refresh(kdp.key, right.pageNum, parentList);
			return;
		}
		if (right.numOfKeyword>(fhead.Level+3)/2) { //put the leftmost key into left
			KeywordDataPair kdp = right.RemoveKeyDataPair(0);
			left.AddKeyDataPair(kdp);
			this.Refresh(kdp.key, right.pageNum, parentList);
			return;
		}
		if (left.numOfKeyword + right.numOfKeyword > fhead.Level)
			throw new IX_Abort_Exception("Fatal");
		//An actual merge is needed.
		Keyword keyToBeDeleted = right.GetKeyword(0);
		for (int i=0; i<right.numOfKeyword; ++i)
			left.AddKeyDataPair(right.GetKeyDataPair(i));
		BPlusTreeNode parent = parentList.remove(parentList.size()-1);
		BPlusTreeNode ret = parent.DeleteFromNode(keyToBeDeleted, parentList);
		if ( ret != null ) {
			root = ret;
			fhead.RootPageNum = root.pageNum;
		}
		left.SetNextPageNum(right.nextPageNum);
		right.DestoryNode();
	}

	@Override
	public void InsertEntry(Keyword key, RID rid) {
		List<BPlusTreeNode> parentList = new ArrayList<BPlusTreeNode>();
		BPlusTreeNode leaf=root;
		int i;
		while (leaf.type != LEAF) {
			for (i=0; i<leaf.numOfKeyword; ++i) {
				if (leaf.GetKeyword(i).compareTo(key)>0)
					break;
			}
			parentList.add(leaf);
			leaf = new BPlusTreeNode(fhead, pfh, leaf.GetPointer(i));
		}
		/* There are different conditions:
		 * 1. leaf has space, just insert the new keyword.
		 * 2. leaf has no space, leaf is root, a new root should be established.
		 * 3. leaf has no space and B+-tree is with height more than 1, just splite it.
		 */
		if (!leaf.IsFull()) {
			leaf.InsertIntoLeaf(key, rid);
			if (key.equals(leaf.GetKeyword(0)))
				Refresh(key, leaf.pageNum, parentList);
			return;
		}
		// The leaf will be splited.
		BPlusTreeNode anotherLeaf = new BPlusTreeNode(pfh, fhead, LEAF);
		Keyword keyInsertedIntoParent = leaf.InsertAndSpliteLeaf(key, rid, anotherLeaf);
		BPlusTreeNode newRoot;
		if (leaf == root) { //Condition 2
			newRoot = new BPlusTreeNode(pfh, fhead, NODE);
			newRoot.SetPointer(0, leaf.pageNum);
			newRoot.AddKeyPointerPair(new KeywordPointerPair(keyInsertedIntoParent,anotherLeaf.pageNum));
			fhead.RootPageNum = newRoot.pageNum;
			fhead.Height++;
			root = newRoot;
			return;
		}
		//Condition 3
		if (key.equals(leaf.GetKeyword(0)))
			Refresh(key, leaf.pageNum, parentList);
		BPlusTreeNode parent = parentList.get(parentList.size()-1);
		newRoot = parent.InsertIntoNode(leaf.pageNum, keyInsertedIntoParent, anotherLeaf.pageNum, parentList);
		parentList.clear();
		if (newRoot==null)
			return;
		fhead.RootPageNum = newRoot.pageNum;
		fhead.Height++;
		root = newRoot;
	}
	
	void Refresh(Keyword key, int pageNum, List<BPlusTreeNode> parentList) {
		BPlusTreeNode p;
		int thisPageNum = pageNum, i=parentList.size(), j;
		while (--i>=0) {
			p = parentList.get(i);
			if (p.GetPointer(0) == thisPageNum) {
				thisPageNum = p.pageNum;
				continue;
			}
			for (j=1; j<=p.numOfKeyword; ++j)
				if (p.GetPointer(j)==thisPageNum)
					break;
			if (j>p.numOfKeyword)
				throw new IX_Abort_Exception("Fatal");
			p.SetKeyword(j-1, key);
		}
	}

	@Override
	public IX_IndexScan OpenScan(Keyword compValue, int compOp) {
		return new IX_IndexScan(compOp, compValue, this);
	}
	
	public BPlusTreeNode GetPreLeaf(BPlusTreeNode leaf) {
		if (leaf.prePageNum==0)
			return null;
		return new BPlusTreeNode(fhead, pfh, leaf.prePageNum);
	}
	
	public BPlusTreeNode GetPostLeaf(BPlusTreeNode leaf) {
		if (leaf.nextPageNum==0)
			return null;
		return new BPlusTreeNode(fhead, pfh, leaf.nextPageNum);
	}
	
}
